package arithmetic2;

/**
 * @author Ajie
 * @date 4/23/21
 * @function
 * 101. 对称二叉树 dfs 前序遍历 简单。
 * https://leetcode-cn.com/problems/symmetric-tree/
 */
public class T_101_SymmetricTree {
    public static void main(String[] args) {
        boolean symmetric = isSymmetric(getTreeRootNode());
        System.out.println(symmetric);
    }

    public static TreeNode getTreeRootNode() {
        /**
         *      5
         *  3      8
         * 1  4   6  10
         */
        TreeNode treeRoot = new TreeNode(1);
        TreeNode tree3 = new TreeNode(2);
        TreeNode tree1 = new TreeNode(3);
        TreeNode tree4 = new TreeNode(4);
        TreeNode tree8 = new TreeNode(2);
        TreeNode tree6 = new TreeNode(4);
        TreeNode tree10 = new TreeNode(3);
        treeRoot.left = tree3;
        tree3.left=tree1;
        tree3.right=tree4;
        treeRoot.right=tree8;
        tree8.left=tree6;
        tree8.right=tree10;
        return treeRoot;
    }

    public static boolean isSymmetric(TreeNode root) {

        if (root==null){
            return true;
        }
       return dfs(root.left,root.right);

    }

    private static boolean dfs(TreeNode left, TreeNode right) {
        if (left==null && right==null){
            return true;
        }
        if (left==null)return false;
        if (right==null)return false;

        if (left.val!=right.val){
            return false;
        }
        boolean dfs = dfs(left.left, right.right);
        if (!dfs){return false;}

        return dfs(left.right,right.left);
    }


}
